{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9891182e",
   "metadata": {},
   "source": [
    "## bfs & dfs\n",
    "- 理论知识可以参考[文档](https://github.com/Willjay5991/DataStructure-BeautyOfAlgorithm/blob/master/docs/18.%E6%B7%B1%E5%BA%A6%E5%92%8C%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2.md)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "578bb7a9",
   "metadata": {},
   "source": [
    "## 深度优先遍历 DFS & 回溯\n",
    "\n",
    "- DFS（Depth-First-Search）采用的是回溯的思想\n",
    "- DFS搜索起点到终点的路径不一定是最短\n",
    "- 主要用于搜索图结构"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dce770c8",
   "metadata": {},
   "source": [
    "### 构建无向图的两个方式\n",
    "- 使用字典+集合构建\n",
    "- 使用字典+链表构建"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0739354",
   "metadata": {},
   "source": [
    "### 图中最短路径问题\n",
    "\n",
    "> 从无向图中一个顶点到另一个顶点的最小路径，每个边长度固定为一， 图使用邻接表的形式存储\n",
    "![最短路径示意图](https://pic.jitudisk.com/public/2022/09/29/267a7158cb4e7.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5e2c4396",
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "6",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "Input \u001b[1;32mIn [2]\u001b[0m, in \u001b[0;36m<cell line: 51>\u001b[1;34m()\u001b[0m\n\u001b[0;32m     56\u001b[0m G2 \u001b[38;5;241m=\u001b[39m GraphviaListNode(Vnum)\n\u001b[0;32m     57\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m v1, v2 \u001b[38;5;129;01min\u001b[39;00m edges:\n\u001b[1;32m---> 58\u001b[0m     \u001b[43mG1\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43maddEdge\u001b[49m\u001b[43m(\u001b[49m\u001b[43mv1\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mv2\u001b[49m\u001b[43m)\u001b[49m\n\u001b[0;32m     59\u001b[0m     G2\u001b[38;5;241m.\u001b[39maddEdge(v1, v2)\n\u001b[0;32m     60\u001b[0m \u001b[38;5;28;01mpass\u001b[39;00m\n",
      "Input \u001b[1;32mIn [2]\u001b[0m, in \u001b[0;36mGraphviaList.addEdge\u001b[1;34m(self, v1, v2)\u001b[0m\n\u001b[0;32m     22\u001b[0m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mlinkList[v1]\u001b[38;5;241m.\u001b[39madd(v2)\n\u001b[0;32m     23\u001b[0m \u001b[38;5;66;03m# 添加v1到v2对应的邻接链表中\u001b[39;00m\n\u001b[1;32m---> 24\u001b[0m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mlinkList\u001b[49m\u001b[43m[\u001b[49m\u001b[43mv2\u001b[49m\u001b[43m]\u001b[49m\u001b[38;5;241m.\u001b[39madd(v1)\n",
      "\u001b[1;31mKeyError\u001b[0m: 6"
     ]
    }
   ],
   "source": [
    "'''\n",
    "Author: yjiedu(yjiedu@foxmail)\n",
    "Date: 2022-11-13 23:10:46\n",
    "LastEditors: yjiedu@office\n",
    "LastEditTime: 2022-11-14 12:44:08\n",
    "Description: \n",
    "version: 1.0.0\n",
    "'''\n",
    "# coding=utf-8\n",
    "\n",
    "# 使用邻接链表表示一个图\n",
    "# 结点V的取值1<=v<=n\n",
    "\n",
    "# 邻接链表使用【值】为【集合】的【字典】实现\n",
    "class GraphviaList:\n",
    "    def __init__(self, Vnum: int):\n",
    "        self.Vnum = Vnum\n",
    "        self.linkList = {v: set() for v in range(Vnum)}\n",
    "\n",
    "    def addEdge(self, v1: int, v2: int) -> None:\n",
    "        # 添加v2到v1对应的邻接链表中\n",
    "        self.linkList[v1].add(v2)\n",
    "        # 添加v1到v2对应的邻接链表中\n",
    "        self.linkList[v2].add(v1)\n",
    "\n",
    "# 使用链表表示图\n",
    "class ListNode:\n",
    "    def __init__(self, val=None, next=None) -> None:\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class GraphviaListNode:\n",
    "    def __init__(self, Vnum: int) -> None:\n",
    "        self.Vnum = Vnum\n",
    "        self.linkList = {v: ListNode(None) for v in range(Vnum)}\n",
    "\n",
    "    def addEdge(self, v1: int, v2: int) -> None:\n",
    "        # 添加v2到v1对应的邻接链表中\n",
    "        h1 = self.linkList[v1]\n",
    "        while h1.next:\n",
    "            h1 = h1.next\n",
    "        h1.next = ListNode(val=v2)\n",
    "        # 添加v1到v2对应的邻接链表中\n",
    "        h2 = self.linkList[v2]\n",
    "        while h2.next:\n",
    "            h2 = h2.next  # 找到链表尾部\n",
    "        h2.next = ListNode(val=v1)  # 添加到链表尾部\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # 构建一个图\n",
    "    Vnum = 8\n",
    "    edges = [[0, 1], [0, 3], [3, 4], [1, 4], [1, 2],\n",
    "             [4, 5], [4, 6], [2, 5], [6, 7], [5, 7]]\n",
    "    G1 = GraphviaList(Vnum)\n",
    "    G2 = GraphviaListNode(Vnum)\n",
    "    for v1, v2 in edges:\n",
    "        G1.addEdge(v1, v2)\n",
    "        G2.addEdge(v1, v2)\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e31cd657",
   "metadata": {},
   "source": [
    "### 实现深度优先遍历，找到从图结点1到5的路径\n",
    "- 两个重要的变量\n",
    "    - visited: 记录每一个结点十分被访问过\n",
    "    - pre： 记录每个结点的前导结点\n",
    "- 使用递归的方法    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8ca3d6d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "Author: yjiedu(yjiedu@foxmail)\n",
    "Date: 2022-11-14 12:47:15\n",
    "LastEditors: yjiedu@office\n",
    "LastEditTime: 2022-11-14 12:58:19\n",
    "Description: \n",
    "version: 1.0.0\n",
    "'''\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# 邻接链表使用【值】为【集合】的【字典】实现\n",
    "class GraphviaList:\n",
    "    def __init__(self, Vnum: int):\n",
    "        self.Vnum = Vnum\n",
    "        self.linkList = {v: set() for v in range(Vnum)}\n",
    "\n",
    "    def addEdge(self, v1: int, v2: int) -> None:\n",
    "        # 添加v2到v1对应的邻接链表中\n",
    "        self.linkList[v1].add(v2)\n",
    "        # 添加v1到v2对应的邻接链表中\n",
    "        self.linkList[v2].add(v1)\n",
    "\n",
    "\n",
    "def dfs(G:GraphviaList,start:int, end:int)->List[int]:\n",
    "    Vnum = G.Vnum\n",
    "    visited = [False]*Vnum\n",
    "    pre = [-1]*Vnum\n",
    "    flag = False # 表示是否找到目标点\n",
    "\n",
    "    # 递归执行\n",
    "    def recurDfs(start:int)->None:\n",
    "        nonlocal G, visited, pre, end,flag\n",
    "        visited[start] = True\n",
    "        linkList = G.linkList[start]\n",
    "        for v in linkList:\n",
    "            if flag:\n",
    "                return\n",
    "            if visited[v]:\n",
    "                continue\n",
    "            pre[v] = start\n",
    "            recurDfs(v)\n",
    "\n",
    "    recurDfs(start) # 执行dfs从start开始搜索end\n",
    "    if pre[end]==-1: # 没找到\n",
    "        return -1\n",
    "    else:  # 找到，从终点反推路径\n",
    "        pos = end\n",
    "        path = [pos]\n",
    "        while pre[pos]!=start:\n",
    "            pos = pre[pos]\n",
    "            path.append(pos)\n",
    "        path.append(start)\n",
    "        return path[::-1] # 翻转\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # 构建图\n",
    "    Vnum = 8\n",
    "    edges = [[0, 1], [0, 3], [3, 4], [1, 4], [1, 2],\n",
    "             [4, 5], [4, 6], [2, 5], [6, 7], [5, 7]]\n",
    "    G = GraphviaList(Vnum)\n",
    "    for v1, v2 in edges:\n",
    "        G.addEdge(v1, v2)\n",
    "    print(dfs(G, 0, 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc9cf806",
   "metadata": {},
   "source": [
    "## bfs\n",
    " - 与dfs一样涉及两个重要的变量\n",
    "     - visited\n",
    "     - pre\n",
    " - bfs 是逐层搜索的，当前层搜索完成后才会搜索下一层，有着严格顺序，因此可以使用队列的方式实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72fe340d",
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "Author: yjiedu(yjiedu@foxmail)\n",
    "Date: 2022-11-14 13:01:52\n",
    "LastEditors: yjiedu@office\n",
    "LastEditTime: 2022-11-14 13:14:56\n",
    "Description: 基于队列实现bfs的路径搜索\n",
    "version: 1.0.0\n",
    "'''\n",
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 邻接链表使用【值】为【集合】的【字典】实现\n",
    "class GraphviaList:\n",
    "    def __init__(self, Vnum: int):\n",
    "        self.Vnum = Vnum\n",
    "        self.linkList = {v: set() for v in range(Vnum)}\n",
    "\n",
    "    def addEdge(self, v1: int, v2: int) -> None:\n",
    "        # 添加v2到v1对应的邻接链表中\n",
    "        self.linkList[v1].add(v2)\n",
    "        # 添加v1到v2对应的邻接链表中\n",
    "        self.linkList[v2].add(v1)\n",
    "\n",
    "\n",
    "def bfs(G: GraphviaList, start: int, end: int) -> List[int]:\n",
    "    Vnum = G.Vnum\n",
    "    visited = [False]*Vnum\n",
    "    pre = [-1]*Vnum\n",
    "\n",
    "    # 定义执行函数\n",
    "\n",
    "    def bfsFun(start: int):\n",
    "        nonlocal G, end\n",
    "        import queue\n",
    "        que = queue.Queue()  # 新建队列\n",
    "        que.put(start)  # 把开始结点放入队列\n",
    "        while not que.empty():\n",
    "            pos = que.get()\n",
    "            if visited[pos]:  # 跳过已经访问过的结点\n",
    "                continue\n",
    "            visited[pos] = True\n",
    "            linkList = G.linkList[pos]\n",
    "            for v in linkList:\n",
    "                if visited[v]:\n",
    "                    continue\n",
    "                pre[v] = pos  # 记录前导结点\n",
    "                if v == end:  # 找到目标点\n",
    "                    return\n",
    "                que.put(v)  # 把该节点放入队列，排队\n",
    "\n",
    "    bfsFun(start)  # 执行bfs，更新visited， pre\n",
    "\n",
    "    if pre[end] == -1:  # 没找到\n",
    "        return -1\n",
    "    else:  # 找到\n",
    "        pos = end\n",
    "        path = [pos]\n",
    "        while pre[pos] != start:\n",
    "            pos = pre[pos]\n",
    "            path.append(pos)\n",
    "        path.append(start)\n",
    "        return path[::-1]\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # 构建图\n",
    "    Vnum = 8\n",
    "    edges = [[0, 1], [0, 3], [3, 4], [1, 4], [1, 2],\n",
    "             [4, 5], [4, 6], [2, 5], [6, 7], [5, 7]]\n",
    "    G = GraphviaList(Vnum)\n",
    "    for v1, v2 in edges:\n",
    "        G.addEdge(v1, v2)\n",
    "    print(bfs(G, 0, 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fff64228",
   "metadata": {},
   "source": [
    "## bfs的一些应用\n",
    "### 二叉树的层序遍历\n",
    "> [102. 二叉树的层序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-level-order-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "84a08f0b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        preLevel = [root]\n",
    "        res = []\n",
    "        res.append([root.val])\n",
    "        while True:\n",
    "            recuLevel = []\n",
    "            tmp = []\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                    tmp.append(node.left.val)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "                    tmp.append(node.right.val)\n",
    "            if recuLevel:\n",
    "                preLevel = recuLevel\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d430cfb4",
   "metadata": {},
   "source": [
    "### 二叉树的锯齿遍历\n",
    "> [103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e09879ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        preLevel = [root]\n",
    "        res = [[root.val]]\n",
    "\n",
    "        flag = False # 反序标志位\n",
    "        while True:\n",
    "            recuLevel = []\n",
    "            vals = []\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                    vals.append(node.left.val)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "                    vals.append(node.right.val)\n",
    "            if recuLevel:\n",
    "                preLevel = recuLevel\n",
    "                if flag:\n",
    "                    res.append(vals)\n",
    "                else:  # 反序\n",
    "                    res.append(vals[::-1])\n",
    "                flag = not flag\n",
    "\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbb71add",
   "metadata": {},
   "source": [
    "###  二叉树最小深度\n",
    "> [111. 二叉树的最小深度 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-depth-of-binary-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "abb75fc0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        depth = 1\n",
    "        preLevel = [root]\n",
    "        while True:\n",
    "            recuLevel = []\n",
    "            for node in preLevel:\n",
    "                if not node.left and not node.right:\n",
    "                    return depth\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "            if recuLevel:\n",
    "                preLevel = recuLevel\n",
    "                depth += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25b900a8",
   "metadata": {},
   "source": [
    "### 二叉树根节点到叶子节点的路径和\n",
    "> [112. 路径总和 - 力扣（LeetCode）](https://leetcode.cn/problems/path-sum/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa9f201c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        \n",
    "        preLevel = [root]\n",
    "        lastVals = [root.val]\n",
    "        while True:\n",
    "            recuLevel = []\n",
    "            vals = []\n",
    "            for i,node in enumerate(preLevel):\n",
    "                if not node.left and not node.right: # 叶子节点\n",
    "                    sumTmp = lastVals[i]\n",
    "                    if sumTmp==targetSum:\n",
    "                        return True\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                    vals.append(node.left.val+lastVals[i])\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "                    vals.append(node.right.val+lastVals[i])\n",
    "            if recuLevel:\n",
    "                lastVals=vals\n",
    "                preLevel = recuLevel\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return True if targetSum in lastVals else False"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
